package sort;

import java.util.Arrays;

/**
 * 工作原理：工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间
 * 平均 O(n2)
 * 最好 O(n)
 * 最坏 O(n2)
 * 空间 O(1)
 * 排序方式 In-place
 * 稳定性 稳定
 */
public class Insert {
    private int [] a = {1,6,2,4,1,5,9};

    private void sort(){
        int current;
        for(int i = 0;i< a.length - 1;i++){
            current = a[i + 1];
            int preIndex = i;
            while(preIndex > 0 && current < a[preIndex]){
                a[preIndex + 1] = a[preIndex];
                preIndex -- ;
            }
            a[preIndex + 1] = current;
        }
    }

    private void print(){
        System.out.println(Arrays.toString(a));
    }

    public static void main(String [] args){
        Insert maoPao = new Insert();
        maoPao.print();
        maoPao.sort();
        maoPao.print();
    }
}
